package com.wc.alorithm_blue_bridge._动态规划.线性DP.Q1189;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

/**
 * @Author congege
 * @Description 最长公共子序列
 * https://www.lanqiao.cn/problems/1189/learning/?page=1&first_category_id=1&sort=students_count&second_category_id=8
 * @Date Created in 2023/10/30-21:39
 */
public class Main {
    public static void main(String[] args) {
        Input sc = new Input();
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] nums1 = new int[m];
        int[] nums2 = new int[n];
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            nums1[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            nums2[i] = sc.nextInt();
        }

        if (nums1[0] == nums2[0]) {
            dp[0][0] = 1;
        }
        // 初始化第一行
        for (int i = 1; i < n; i++) {
            if (nums1[0] == nums2[i]) {
                dp[0][i] = 1;
            } else {
                dp[0][i] = dp[0][i - 1];
            }
        }
        // 初始化第一列
        for (int i = 1; i < m; i++) {
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        Main main = new Main();
        main.paint(nums1, nums2);
        System.out.println(dp[m - 1][n - 1]);
    }

    /**
     * @param nums1
     * @param nums2
     */

    // 5 6
    // 1 2 3 4 5
    // 2 3 2 1 4 5
    public void paint(int[] nums1, int[] nums2) {
        int m = nums1.length + 1;
        int n = nums2.length + 1;
        char[][] map = new char[m][n];
        int[][] dp = new int[m][n];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                    map[i][j] = '↖';
                } else if (dp[i - 1][j] > dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                    map[i][j] = '↑';
                } else {
                    dp[i][j] = dp[i][j - 1];
                    map[i][j] = '←';
                }
            }
        }
        for (int i = 0; i < m; i++) {
            System.out.println(Arrays.toString(map[i]));
        }
    }

    static class Input {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

        public int nextInt() {
            try {
                in.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }
    }
}
